package list;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @user 26233
 * @create 2020-07-25 16:26:03
 * @description 双向链表
 **/

public class MyLinkedList {

    private Node head = null;

    private Node tail = null;

    class Node{

        Node pre;
        Node next;
        Object data;

        public Node(){
        }

        public Node(Object obj){
            this.data = obj;
        }

    }

    // 添加到结尾
    private Node add(Object obj){
        Node newNode = new Node(obj);
        if(head == null){
            head = newNode;
        }else{
            tail.next = newNode;
            newNode.pre = tail;
        }
        tail = newNode;
        return head;
    }

    // // 在某个节点后添加
    private Node addAfter(Object obj, Object dst) throws Exception {
        Node dstNode = searchNode(dst);
        if (dstNode == null){
           throw new Exception("no target data in list");
        }
        Node newNode = new Node(obj);
        newNode.next = dstNode.next;
        newNode.pre = dstNode;
        // 尾结点
        if (dstNode.next != null)
            dstNode.next.pre = newNode;
        else
            tail = newNode;
        dstNode.next = newNode;
        return head;
    }

    private Node searchNode(Object obj){
        Node tempHead = head;
        Node dstNode = null;
        while (tempHead != null){
            if (tempHead.data.equals(obj)){
                dstNode = tempHead;
                break;
            }else {
                tempHead = tempHead.next;
            }
        }
        return dstNode;
    }

    // 在某个节点前添加
    private Node addBefore(Object obj, Object dst) throws Exception {
        Node dstNode = searchNode(dst);
        if (dstNode == null){
            throw new Exception("no target data in list");
        }
        Node newNode = new Node(obj);
        newNode.next = dstNode;
        newNode.pre = dstNode.pre;
        // 头节点
        if (dstNode.pre != null)
            dstNode.pre.next = newNode;
        else
            head = newNode;
        dstNode.pre = newNode;

        return head;
    }

    // 删除某个节点
    public Node remove(Object obj){
        Node dstNode = searchNode(obj);
        if (dstNode.pre == null && dstNode.next == null)
            head = tail = null;
        else if (dstNode.pre == null){
            head = dstNode.next;
            head.pre = null;
        }
        else if (dstNode.next == null){
            tail = dstNode.pre;
            tail.next = null;
        }
        else {
            dstNode.pre.next = dstNode.next;
            dstNode.next.pre = dstNode.pre;
        }
        dstNode = null;
        return head;
    }

    // 遍历链表
    private List navigationList(){
        Node tempHead = head;
        List<Object> data = new ArrayList<>();
        while (tempHead != null){
            data.add(tempHead.data);
            tempHead = tempHead.next;
        }
        return data;
    }

    public static void main(String[] args) throws Exception {
        int[] data = new int[]{1, 2, 3, 4, 5, 6};
        MyLinkedList dl = new MyLinkedList();
        Arrays.stream(data).forEach(dl::add);

        System.out.println("origin: " + dl.navigationList());
        dl.addAfter("a", 1);
        System.out.println("add 'a': " + dl.navigationList());

        dl.addBefore("b", "a");
        System.out.println("add 'b': " + dl.navigationList());

        dl.remove(5);
        dl.remove(1);
        dl.remove(6);
        System.out.println("remove: " + dl.navigationList());

        System.out.println("hang on");
    }
}
